{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Most Competitive Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mostCompetitive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出最具竞争力的子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个正整数 <code>k</code> ，返回长度为 <code>k</code> 且最具 <strong>竞争力</strong> 的<em> </em><code>nums</code> 子序列。</p>\n",
    "\n",
    "<p>数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。</p>\n",
    "\n",
    "<p>在子序列 <code>a</code> 和子序列 <code>b</code> 第一个不相同的位置上，如果 <code>a</code> 中的数字小于 <code>b</code> 中对应的数字，那么我们称子序列 <code>a</code> 比子序列 <code>b</code>（相同长度下）更具 <strong>竞争力</strong> 。 例如，<code>[1,3,4]</code> 比 <code>[1,3,5]</code> 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， <code>4</code> 小于 <code>5</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,5,2,6], k = 2\n",
    "<strong>输出：</strong>[2,6]\n",
    "<strong>解释：</strong>在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4,3,3,5,4,9,6], k = 4\n",
    "<strong>输出：</strong>[2,3,3,4]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= nums[i] <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 <= k <= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-most-competitive-subsequence](https://leetcode.cn/problems/find-the-most-competitive-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-most-competitive-subsequence](https://leetcode.cn/problems/find-the-most-competitive-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,2,6]\\n2', '[2,4,3,3,5,4,9,6]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        stack = []\n",
    "        for i in range(len(nums)):\n",
    "            while stack and k - len(stack) < len(nums) - i and stack[-1] > nums[i]:\n",
    "                stack.pop()\n",
    "            stack.append(nums[i])\n",
    "        return stack[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        while n > k:\n",
    "            while i != n - 1 and nums[i] <= nums[i + 1]:\n",
    "                i += 1\n",
    "            del nums[i]\n",
    "            if i > 0:\n",
    "                i -= 1\n",
    "            n -= 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        while k < len(nums):\n",
    "            num = nums.pop(0)\n",
    "            while res and res[-1] > num and k < len(nums)+1:\n",
    "                res.pop()\n",
    "                k += 1\n",
    "            if k == 0:\n",
    "                continue\n",
    "            else:\n",
    "                k -= 1\n",
    "                res.append(num)\n",
    "        res += nums\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        # res = []\n",
    "        # length = len(nums)\n",
    "        # for i in range(length):\n",
    "        #     # print(\"i:\",i)\n",
    "        #     if not res:\n",
    "        #         res.append(nums[i])\n",
    "        #     elif nums[i]>res[-1]:\n",
    "        #         res.append(nums[i])\n",
    "        #     else:\n",
    "        #         j = len(res)\n",
    "        #         while j>0:\n",
    "        #             # print(\"0000：\",j,length-i+j)\n",
    "        #             if length-i+j>k and res and res[-1]>nums[i]:\n",
    "        #                 res.pop()\n",
    "        #             j = j - 1\n",
    "        #         res.append(nums[i])\n",
    "        \n",
    "        #     # print(res)\n",
    "        # return res[:k]\n",
    "\n",
    "        i = 0\n",
    "        while len(nums) > k and i < len(nums) - 1:\n",
    "            if nums[i] > nums[i + 1]:\n",
    "                nums.remove(nums[i])\n",
    "                if i > 0:\n",
    "                    i -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "            \n",
    "        return nums[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        i = 0\n",
    "        while len(nums) > k and i < len(nums)-1:\n",
    "            if nums[i+1] < nums[i]:\n",
    "                nums.remove(nums[i])\n",
    "                if i > 0:\n",
    "                    i -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return nums[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        stack = [nums.pop(0)]\n",
    "        while nums:\n",
    "            num = nums.pop(0)\n",
    "            while len(stack) != 0 and len(stack) + len(nums) >= k and num < stack[-1]:\n",
    "                stack.pop()\n",
    "            stack.append(num)\n",
    "        return stack[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 一次遍历，删除数组中nums[i] > nums[i + 1]的nums[i]，使之不减。\n",
    "        # 同时需满足结果对元素数量的要求，即while len(nums) > k\n",
    "        i = 0\n",
    "        while len(nums) > k and i < len(nums) - 1:\n",
    "            if nums[i] > nums[i + 1]:\n",
    "                nums.remove(nums[i])\n",
    "                # 如i==0, 首位元素被删除后，下一轮将由新的nums[0]和nums[0+1]进行比较\n",
    "                # 如i不是首元素，i需自减1。即下一轮需比较当前位置的前一个和后一个元素（当前元素已经在本轮中删除）\n",
    "                if i > 0:\n",
    "                    i -= 1\n",
    "            else: # 如nums[i] <= nums[i + 1]，i后移，继续比较\n",
    "                i += 1\n",
    "        return nums[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        i = 0\n",
    "        while len(nums) > k and i < len(nums) - 1:\n",
    "            if nums[i] > nums[i+1]:\n",
    "                del nums[i]\n",
    "                if i > 0:\n",
    "                    i -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return nums[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        size = len(nums)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        right = 0\n",
    "\n",
    "        queue = collections.deque()\n",
    "        while k > 0:\n",
    "            for _ in range(right, size - k + 1):\n",
    "                while queue and queue[-1] > nums[right]:\n",
    "                    queue.pop()\n",
    "                queue.append(nums[right])\n",
    "                right += 1\n",
    "\n",
    "            ans.append(queue.popleft())\n",
    "            k -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        s = deque()\n",
    "        n = len(nums)\n",
    "\n",
    "        for idx, i in enumerate(nums):\n",
    "            while s and s[-1] > i:\n",
    "                s.pop()\n",
    "            s.append(i)\n",
    "            if (n - idx) <= k:\n",
    "                res.append(s[0])\n",
    "                s.popleft()\n",
    "                k -= 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        i,l = 0,0\n",
    "        maxNum = 0\n",
    "        #print(n,k)\n",
    "        while i<n and n-i>=k-l:\n",
    "            #print(ans)\n",
    "            num = nums[i]\n",
    "            flag = False\n",
    "            if num<maxNum:\n",
    "                for j in range(max(0,k+i-n),l):\n",
    "                    if ans[j]>num:\n",
    "                        ans[j] = num\n",
    "                        ans = ans[:j+1]\n",
    "                        l = j+1\n",
    "                        flag = True\n",
    "                        break\n",
    "                    else:\n",
    "                        maxNum = max(maxNum,num)\n",
    "            if not flag:\n",
    "                if l<k:\n",
    "                    ans.append(num)\n",
    "                    l += 1\n",
    "                    maxNum = max(maxNum,num)\n",
    "                else:\n",
    "                    if num==0:\n",
    "                        break\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k==1:return [min(nums)]\n",
    "        n=len(nums)\n",
    "        cur=nums[n-k:]\n",
    "        flag=0\n",
    "        flag2=1000000001\n",
    "        for i in range(n-k-1,-1,-1):\n",
    "            temp=nums[i]\n",
    "            if temp<=cur[0] and temp<flag2:\n",
    "                if not flag:\n",
    "                    last=cur[0]\n",
    "                    cur[0]=temp\n",
    "                    i2=1\n",
    "                    while i2<k and last<=cur[i2]:\n",
    "                        cur[i2],last=last,cur[i2]\n",
    "                        i2+=1\n",
    "                    flag2=last\n",
    "                    if i2==k:\n",
    "                        flag=1\n",
    "                else:\n",
    "                    cur.insert(0,temp)\n",
    "                    # cur.pop()\n",
    "                # print(cur,flag2)\n",
    "\n",
    "        return cur[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        dq = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while dq and nums[i] < dq[-1] and n-i > k-len(dq):\n",
    "                dq.pop()\n",
    "            dq.append(nums[i])\n",
    "        return dq[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 单调栈, 维持单调栈中元素升序,\n",
    "        # 记录删除的元素, 最多删除n - k个,\n",
    "        # 最后取栈中的前k个元素\n",
    "\n",
    "        n, stack, dlt = len(nums), [], 0\n",
    "        for num in nums:\n",
    "            while stack and num < stack[-1] and dlt < n - k:\n",
    "                stack.pop()\n",
    "                dlt += 1\n",
    "            stack.append(num)\n",
    "\n",
    "        return stack[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_del = len(nums) - k\n",
    "        \n",
    "        st = []\n",
    "        for i in nums:\n",
    "            while num_del and st and i < st[-1]:\n",
    "                num_del -= 1\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        return st[:k]           \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] < nums[stack[-1]] and len(stack) + n - i > k:\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(i)\n",
    "\n",
    "        for i in range(k):\n",
    "            ans.append(nums[stack[i]])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * k\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while len(st) > 0 and nums[st[- 1]] > nums[i] and len(st) + n - i > k:\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        while len(st) > k:\n",
    "            st.pop()\n",
    "        for i in range(k - 1, - 1, - 1):\n",
    "            ans[i] = nums[st[- 1]]\n",
    "            st.pop()    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "      n = len(nums)\n",
    "      stack = []\n",
    "      for i, x in enumerate(nums):\n",
    "        while stack and stack[-1] > x and len(stack) + n - i > k:\n",
    "          stack.pop()\n",
    "        stack.append(x)\n",
    "      return stack[:k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        count = n - k\n",
    "        stack = []\n",
    "        for i in range(0, n):\n",
    "            while(stack and count and nums[i] < stack[-1]):\n",
    "                stack.pop()\n",
    "                count -= 1\n",
    "            stack.append(nums[i])\n",
    "        return stack[:k]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and nums[s[-1]] > nums[i] and n - i >= k - len(s) + 1:\n",
    "                s.pop()\n",
    "            s.append(i)\n",
    "        return [nums[i] for i in s[:k]]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 需要移除的元素个数\n",
    "        n = len(nums)\n",
    "        m = n-k\n",
    "        stack = [0]\n",
    "        for num in nums:\n",
    "            while m and num < stack[-1]:\n",
    "                stack.pop()\n",
    "                m -= 1\n",
    "            stack.append(num)\n",
    "        return stack[1:k+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        # case75超时\n",
    "        # n = len(nums)\n",
    "        # t_nums = nums[0:k]\n",
    "        # for i in range(k, n):\n",
    "        #     ma = max(t_nums)\n",
    "        #     adj = False\n",
    "        #     for j in range(k-1):\n",
    "        #         if t_nums[j+1] < t_nums[j]:\n",
    "        #             t_nums.pop(j)\n",
    "        #             t_nums.append(nums[i])\n",
    "        #             adj = True                    \n",
    "        #             break\n",
    "        #     if not adj and ma > nums[i]:\n",
    "        #         t_nums.remove(ma)\n",
    "        #         t_nums.append(nums[i])\n",
    "        # return t_nums\n",
    "\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        last = n-k  # 最多可以pop的原数个数\n",
    "        for i in range(n):\n",
    "            while stack and last and stack[-1] > nums[i]:\n",
    "                stack.pop()\n",
    "                last -= 1\n",
    "            stack.append(nums[i])\n",
    "        return stack[:k]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        last = n -k\n",
    "        for i in range(n):\n",
    "            while stack and last and stack[-1] > nums[i]:\n",
    "                stack.pop()\n",
    "                last -= 1\n",
    "            stack.append(nums[i])\n",
    "        print(stack)\n",
    "        return stack[:k]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        from heapq import heapify, heappush, heappop\n",
    "\n",
    "        n = len(nums)\n",
    "        heap = [(nums[i], i) for i in range(n-k+1)]\n",
    "        heapify(heap)\n",
    "        \n",
    "        prev_idx = -1  # the next idx should be greater than prev_idx\n",
    "        result = []\n",
    "\n",
    "        for kk in range(k):\n",
    "\n",
    "            while True:\n",
    "                num, i = heappop(heap)\n",
    "                if i < prev_idx:\n",
    "                    # print(f\"pop {i}: {num}, idx too small\")\n",
    "                    continue\n",
    "                else:\n",
    "                    # print(f\"pop {i}: {num}, OK!\")\n",
    "                    break\n",
    "            \n",
    "            result.append(num)\n",
    "            prev_idx = i\n",
    "\n",
    "            if kk < k - 1:\n",
    "                heappush(heap, (nums[n-k+kk+1], n-k+kk+1))\n",
    "                # print(f\"push {n-k+kk+1}: {nums[n-k+kk+1]}\")\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from heapq import heappop, heappush\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        heap = []\n",
    "        ans = []\n",
    "        for i in range(n - k + 1):\n",
    "            heappush(heap, (nums[i], i))\n",
    "        left, right = 0, n - k\n",
    "        while len(ans) < k:\n",
    "            while heap[0][1] < left:\n",
    "                heappop(heap)\n",
    "            num, idx = heappop(heap)\n",
    "            ans.append(num)\n",
    "            left = idx + 1\n",
    "            right += 1\n",
    "            if right < n:\n",
    "                heappush(heap, (nums[right], right))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, a: List[int], k: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList([[a[i], i] for i in range(len(a)-k)])\n",
    "        ans = []\n",
    "        for i in range(len(a)-k, len(a)):\n",
    "            sl.add([a[i], i])\n",
    "            x, j = sl[0]\n",
    "            ans.append(x)\n",
    "            while sl and sl[0][1]<=j:\n",
    "                sl.remove(sl[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = sortedcontainers.SortedList([])\n",
    "        seen = set()\n",
    "        for i in range(n-k+1):\n",
    "            s.add([nums[i], i])\n",
    "            seen.add(i)\n",
    "        ans = []\n",
    "        ans.append(s[0][0])       \n",
    "        l = 1\n",
    "        if l >= k:\n",
    "            return ans\n",
    "        next_start = s[0][1]+1\n",
    "        for j in range(s[0][1]+1):\n",
    "            seen.remove(j)\n",
    "            s.remove([nums[j], j])\n",
    "\n",
    "        for j in range(n-k+1, n):\n",
    "            s.add([nums[j], j])\n",
    "            seen.add(j)\n",
    "            ans.append(s[0][0])\n",
    "            l += 1\n",
    "            start = next_start\n",
    "            next_start = s[0][1]+1\n",
    "            for m in range(start, s[0][1]+1):\n",
    "                if m in seen:\n",
    "                    seen.remove(m)\n",
    "                    s.remove([nums[m], m])\n",
    "            if l >= k:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        ans = []\n",
    "        pre = -1\n",
    "        for i in range(n):\n",
    "            heapq.heappush(stack, [nums[i], i])\n",
    "            if n-i-1 == k-1:\n",
    "                while stack and stack[0][1] <= pre:\n",
    "                    heapq.heappop(stack)\n",
    "                if stack:\n",
    "                    num, j = heapq.heappop(stack)\n",
    "                    ans.append(num)\n",
    "                    pre = j\n",
    "                    k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        N = len(nums)\n",
    "        stack = []\n",
    "        toremove = N-k\n",
    "        counter = Counter(nums)\n",
    "        for n in nums:\n",
    "            while stack and n < stack[-1] and toremove > 0:\n",
    "                stack.pop()\n",
    "                toremove -= 1\n",
    "            stack.append(n)\n",
    "        for i in range(toremove):\n",
    "            stack.pop()\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        st = inf\n",
    "        pos = -1\n",
    "        n = len(nums)\n",
    "        s = SortedList()\n",
    "        for i, num in enumerate(nums):\n",
    "            if n - i >= k:\n",
    "                if num < st:\n",
    "                    pos = i\n",
    "                    st = num\n",
    "            \n",
    "        res = [st]\n",
    "        left = k - 1\n",
    "        l = pos + 1\n",
    "        j = pos + 1\n",
    "        while left:\n",
    "            while j < n and n - j >= left:\n",
    "                s.add((nums[j], j))\n",
    "                j += 1\n",
    "            \n",
    "            res.append((s[0][0]))\n",
    "            tmp = s[0][1]\n",
    "            while l <= tmp:\n",
    "                s.remove((nums[l], l))\n",
    "                l += 1\n",
    "            left -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        q = []\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            heappush(q,(nums[i],i))\n",
    "        t = -1\n",
    "        i = k\n",
    "        s = []\n",
    "        while q and i > 0:\n",
    "            while q and (q[0][1] <= t or q[0][1] > n - i):\n",
    "                if q[0][1] > n - i:\n",
    "                    x,y = heappop(q)\n",
    "                    insort(ans,(y,x))\n",
    "                    insort(s,y)\n",
    "                else:\n",
    "                    heappop(q)\n",
    "            a = bisect_right(s,t)\n",
    "            b = bisect_left(s,n-i+1)\n",
    "            if a != b:\n",
    "                t = s[a]\n",
    "                i -= 1\n",
    "            elif q:\n",
    "                x,y = heappop(q)\n",
    "                insort(ans,(y,x))\n",
    "                insort(s,y)\n",
    "                t = y\n",
    "                i -= 1\n",
    "        return [i[1] for i in ans[:k]]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        q = []\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            heappush(q,(nums[i],i))\n",
    "        t = -1\n",
    "        i = k\n",
    "        s = []\n",
    "        while q and i > 0:\n",
    "            while q and (q[0][1] <= t or q[0][1] > n - i):\n",
    "                if q[0][1] > n - i:\n",
    "                    x,y = heappop(q)\n",
    "                    insort(ans,(y,x))\n",
    "                    insort(s,y)\n",
    "                else:\n",
    "                    heappop(q)\n",
    "            a = bisect_right(s,t)\n",
    "            b = bisect_left(s,n-i+1)\n",
    "            # print(s,t,n-i+1,a,b)\n",
    "            if a != b:\n",
    "                t = s[a]\n",
    "                i -= 1\n",
    "            elif q:\n",
    "                x,y = heappop(q)\n",
    "                insort(ans,(y,x))\n",
    "                insort(s,y)\n",
    "                t = y\n",
    "                i -= 1\n",
    "            # print(ans,t)\n",
    "        return [i[1] for i in ans[:k]]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n",
    "        q = [[nums[i], i] for i in range(len(nums)-k)]\n",
    "        heapq.heapify(q)\n",
    "        ans, last = [], -1\n",
    "        for i in range(k):\n",
    "            heapq.heappush(q, [nums[len(nums)-k+i], len(nums)-k+i])\n",
    "            while q[0][1]<last: heapq.heappop(q)\n",
    "            ans.append(q[0][0])\n",
    "            last = q[0][1]\n",
    "            heapq.heappop(q)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
